Rekurzivni potprogrami su potprogrami koji pozivaju sami sebe. Šta dobijamo ovakvim potprogramima? Odgovor je da ponekad lakše možemo da izrazimo rešenje ako se pri rešavanju pozivamo na samo rešenje. Ideja je slična rekurzivnim definicijama u matematici.
Fibonačijev niz i izračunavanje faktorijela su klasični primeri rekurzivnih potprograma.
Primer : Izračunavanje n!
Računanje faktorijela je klasičan primer rekurzivnog potprograma, mada je iterativno rešenje isto tako očigledno. Pomoću iteracije možemo da izračunamo proizvod
F= 1 * 2 * 3 * 4 * ... * n
tako što ćemo u petlji množiti redom brojeve od 1 do n. Posebno moramo da obradimo samo slučaj kada je n=0. Tada rezultat mora biti jednak 1, jer po definiciji
0!=1
Iterativni potprogram za izračunavanje n! možemo dakle, da napišemo ovako:
function F(n: integer) : integer
var i, p : integer;
begin
if n=0 then F:=1 else begin
p:=1; for i:=1 to n do p:=p*i;
F:=p;
end;
end;
Ideja za rekurzivnu formulaciju dolazi iz sledeće formule : n! = n * (n-1)!
U skladu sa tom formulom, rekurzivna definicija za n! je sledeća:
ako je n=0, onda je n!=1 inače je n!= n* (n-1)!. Dakle:
function F (n: integer): integer;
begin
if n=0 then F:=1 else F:= n* F(n-1)
end;
je rekurzivna funkcija za izračunavanje faktorijela.